package com.cuz.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Q30ConcatenateSubstringsAllWords {

    public static void main(String[] args) {
        //"barfoothefoobarman", words = ["foo","bar"]
        //"wordgoodgoodgoodbestword"
        //["word","good","best","good"]
        List<Integer> res = findSubstring1("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"});

        System.out.println(res);
    }

    public static List<Integer> findSubstring1(String s, String[] words) {
        HashMap<String, Integer> strMap = new HashMap<>();
        //没一个单词的出现个数
        for (String loop : words) {
            int count = strMap.getOrDefault(loop, 0) + 1;
            strMap.put(loop, count);
        }
        int maxLen = s.length();
        //单个单词的长度
        int singleWordLen = words[0].length();
        int wordNum = words.length;
        //单词总长度
        int wordLenSum = singleWordLen * wordNum;
        ArrayList<Integer> list = new ArrayList<>();
        //index 大于这个maxLen - wordLenSum 后面 字串长度就不够了
        for (int index = 0; index <= maxLen - wordLenSum; index++) {
            //裁剪
            String tempString = s.substring(index, index + wordLenSum);
            //字串是否包含所有的
            if (strContainAll(strMap, tempString, singleWordLen)) {
                list.add(index);
            }
        }
        return list;
    }

    private static boolean strContainAll(HashMap<String, Integer> strMap, String str, int singleWordLen) {
        int loop = singleWordLen;
        int pre = 0;
        HashMap<String, Integer> wordMemory = new HashMap<>();
        while (loop <= str.length()) {
            String subString = str.substring(pre, loop);
            int wordCount = wordMemory.getOrDefault(subString, 0) + 1;
            int sourceCount = strMap.getOrDefault(subString, 0);
            if (wordCount > sourceCount) {
                return false;
            }
            wordMemory.put(subString, wordCount);
            pre = loop;
            loop += singleWordLen;
        }
        return true;
    }
}
